A recording medium for recording digital data such as music contents and image data has various forms such as a magnetic disk, optical disk, and magneto optical disk. A semiconductor memory card, another example of the recording medium, uses non-volatile semiconductor memory such as a flash memory as memory device and is becoming widely used mainly in small-sized portable device such as a digital still camera and cellular phone terminal because the recording medium can be miniaturized.
In the flash memory used as the memory device, an erase unit is different from a writing unit. In addition, the flash memory characteristically cannot overwrite data to a page that is a writing unit in a physical block in which data is already stored. For this reason, the flash memory has such a problem that memory area is wastefully consumed when written data is overwritten, that is, data is rewritten.
When data is rewritten, conventionally, data already existing in a block has been evacuated to an external memory, and rewriting data has been written to a pertinent block in a non-volatile memory after the rewriting data is recorded in an external memory once. A method is disclosed in Patent document 1 for this method. In the method, when data is rewritten, rewriting data is written to a free physical block, and then the other data before rewriting stored in the physical block is written (copied) to the physical block in which the rewriting data is written. As a result, the physical block having data before rewriting has no valid data, erasing can be completed without losing valid data, reusing the initial physical block becomes possible, and limited physical blocks can be effectively used.    Patent document 1: Unexamined Patent Publication 2001-509941.